GATE PYQ

Recursive Language

Q1.
The set of all recursively enumerable languages is

Q2.
Let < M > denote an encoding of an automaton M. Suppose that \Sigma =\{0,1\}. Which of the following languages is/are NOT recursive?

Q3.
If L and P are two recursively enumerable languages then they are not closed under

Q4.
Given the following statementsS1 : Every context-sensitive language L is recursiveS2 : There exists a recursive language that is not context-sensitiveWhich statements are true?

Q5.
Which of the following statements is/are TRUE? MSQ

Q6.
A problem whose language is recursion is called?

Q7.
Nobody knows yet if P = NP. Consider the language L defined as follows : L=\left\{\begin{matrix} (0+1)^{*}\; \; \; if P=NP\\ \Phi \; \; otherwise \end{matrix}\right. Which of the following statements is true ?

Q8.
Let L be a language and \bar{L} be its complement. Which of the following is NOT a viable possibility?

Q9.
If L and \bar L are recursively enumerable then L is

Q10.
Let X be a recursive language and Y be a recursively enumerable but not recursive language. Let W and Z be two languages such that \bar{Y} reduces to W, and Z reduces to \bar{X} (reduction means the standard many-one-reduction). Which one of the following statements is TRUE?